package algorithm.poj;

public class AdvMath {

	/**
	 * return all primes less than m 
	 * @param m
	 * @return
	 */
	public static int[] primes(int m) {
		
		if (m <= 1) {
			return new int[0];
		} else if (m == 2) {
			return new int[] {2};
		} else {
			int count = 0;
			int[] ns = new int[m];
			for (int i = 0; i < m; i ++) ns[i] = i;
			ns[0] = ns[1] = 0;
			
			int index = 2;
			int p = 0;
			while (index < m) {
				if (ns[index] != 0) {
					count ++;
					p = index;
					for (int j = (p<<1); j < m; j += p) {
						ns[j] = 0;
					}
				}
				index ++;
			}
			
			index = 0;
			int[] ps = new int[count];
			for (int i = 0; i < m; i ++) {
				if (ns[i] != 0) {
					ps[index ++] = i;
				}
			}

			return ps;
		}
	}
	
	/**
	 * C(m,n)
	 * @param m
	 * @param n
	 * @return
	 */
	public static long c(long m, long n) {
		
		if (m < n) return 0;
		long r = 1;
		for (long i = 0; i < (long)Math.min(m-n, n); i ++) {
			r *= (m-i);
			r /= i+1;
		}
		return r;
	}
	
	public static int[] next_permutation(int[] ds) {
		
		int j = ds.length-2;
		for (; j > -1; j --) {
			if (ds[j+1] > ds[j]) break;
		}
		if (j == -1) {
			for (int i = 0; i < (ds.length+1)/2; i ++) {
				int s = ds[ds.length-1-i];
				ds[ds.length-1-i] = ds[i];
				ds[i] = s;
			}
		} else {
			int k = ds.length-1;
			for (; k > -1; k --) {
				if (ds[k] > ds[j]) break;
			}
			int t = ds[k];
			ds[k] = ds[j];
			ds[j] = t;
			for (int i = j+1; i < (ds.length+j)/2+1; i ++) {
				int s = ds[ds.length+j-i];
				ds[ds.length+j-i] = ds[i];
				ds[i] = s;
			}
		}
		return ds;
	}

	
	/**
	 * 获得当前组合c的下一个组合。
	 * 利用该函数可以依次获得[0, M)的所有组合
	 * @param c
	 * @param M
	 * @return
	 */
	public static int[] next_combination(int[] c, int M) {

		int index = c.length-1;
		for (; index > -1; index --) {
			if (c[index] < M-(c.length-index)) {
				c[index] ++;
				for (int i = index+1; i < c.length;i ++) {
					c[i] = c[index] + i - index;
				}
				break;
			}
		}
		if (index == -1) {
			if (c.length < M) {
				int[] nc = new int[c.length+1];
				for (int i = 0; i < nc.length; i ++) {
					nc[i] = i;
				}
				return nc;
			} else {
				return null;
			}
		} else {
			return c;
		}
	}
	
	/**
	 * ps is all primes number less than sqrt(n)
	 * @param n
	 * @param ps
	 * @return
	 */
	public static int[][] factors(long n, int[] ps) {

		int[] as = new int[ps.length];
		for (int i = 0; i < as.length; i ++) {
			if (n >= ps[i]) {
				while (n%ps[i] == 0) {
					n /= ps[i];
					as[i] ++;
				}
			}
		}
		
		int count = 0;
		for (int i = 0; i < as.length; i ++) {
			if (as[i] > 0) {
				count ++;
			}
		}
		if (n > 1) count ++;
		
		int[][] fs = new int[count][];
		int index = 0;
		for (int i = 0; i < as.length; i ++) {
			if (as[i] > 0) {
				fs[index] = new int[2];
				fs[index][0] = ps[i];
				fs[index][1] = as[i];
				index ++;
			}
		}
		if (n > 1) {
			fs[count-1] = new int[2];
			fs[count-1][0] = (int)n;
			fs[count-1][1] = 1;
		}
		return fs;
	}

	/**
	 * return (t, s) satisfy equation: a*t + b*s = gcd(a,b)
	 * @param a
	 * @param b
	 * @return
	 */
	public static long[] solve(long a, long b) {
		
		if (a < 0) {
			a = -a;
			long[] r = solve(a, b);
			return new long[] {-r[0], r[1]};
		}
		if (b < 0) {
			b = -b;
			long[] r = solve(a, b);
			return new long[] {r[0], -r[1]};
		}
		if (a == 0) {
			return new long[] {0, 1};
		} else if (b == 0) {
			return new long[] {1, 1};
		} else {
			if (a < b) {
				long[] r = solve(b, a);
				return new long[] {r[1], r[0]};
			} else {
				long[] r = solve(b, a%b);
				long m = a/b;
				return new long[] {r[1], r[0]-r[1]*m};
			}
		}
	}
	
	public static long lcm(long x, long y) {
		
		return x/gcd(x, y)*y;
	}
	
	public static long gcd(long x, long y) {

		x = (x<0)?(-x):x;
		y = (y<0)?(-y):y;
		if (x == 0) {
			return y;
		} else if (y == 0) {
			return x;
		} else {
			if (x < y) return gcd(y, x);
			else return gcd(y, x%y);
		}
	}

}
